Field of the Invention
The disclosed embodiments generally relate to techniques for querying and viewing geographic data sets. More specifically, the disclosed embodiments relate to a point-in-polygon indexing technique to facilitate viewing statistical data associated with geographic regions.
Related Art
The point-in-polygon (PIP) problem has important applications in a variety of disciplines, including geographic information systems (GISs), computer games, computer vision applications and computer-aided design (CAD). Solutions to the PIP problem have been motivated by the requirements of choropleth maps for geographic information systems (GISs). A choropleth map is a type of “heat map” in which polygons are shaded based on the quantity or density of certain subjects of interest within the polygon. For example, one can count the number of Starbucks™ stores within each state (the state boundaries being the set of polygons), and then visually present the information by filling in each polygon with a color or hue that reflects the count of Starbucks™ stores in the given polygon. In this example, the digitized boundaries of the US states may contain hundreds of thousands of points for each state. Hence, application of a brute force crossing number (CN) technique to solve the PIP problem involves iterating over all of the many vertices in each state boundary. While some performance optimizations exist for the special case of non-overlapping polygons, in general such optimizations are impossible or impractical. Furthermore, the CN technique needs to be run on each data point. Consequently, processing even a small number of data points against a large GIS boundary dataset is computationally expensive.
Hence, what is needed is a system that facilitates efficiently solving the PIP problem without the limitations of existing techniques.
Table 1 illustrates sorted point structures in accordance with the disclosed embodiments.
Table 2 illustrates sorted point structures with corresponding lists of open segments in accordance with the disclosed embodiments.
Table 3 illustrates how non-final rows can be struck out in accordance with the disclosed embodiments.
Table 4 illustrates Y ranges and corresponding open segments in accordance with the disclosed embodiments.
Table 5 illustrates how non-final rows can be struck out in accordance with the disclosed embodiments.
Table 6 illustrates how the data structure can be modified for modulo 3 storage in accordance with the disclosed embodiments.